import collections
class Solution(object):
    def longestSubsequenceRepeatedK(self, s, k):
        n = len(s)
        c = collections.Counter(s)
        st = {}
        for key in c:
            val = c[key] // k
            if val > 0:
                st[ord(key) - ord('a')] = val
        p = [[-1 for _ in range(26)] for _ in range(n)]
        for i in range(n - 2, -1, -1):
            ord_next = ord(s[i + 1]) - ord('a')
            for j in range(26):
                if j == ord_next:
                    p[i][j] = i + 1
                else:
                    p[i][j] = p[i + 1][j]
        ps_start = {}
        for i in range(n):
            if ord(s[i]) - ord('a') not in  ps_start:
                ps_start[ord(s[i]) - ord('a')] = i
        self.max_ans = ''
        self.max_len = 0
        now_st = []
        def dfs():
            for key in st:
                if st[key]:
                    now_st.append(key)
                    st[key] -= 1
                    if find():
                        dfs()
                    now_st.pop()
                    st[key] += 1

        
        def find():
            next_st = now_st * k
            index = ps_start[now_st[0]]
            for i in range(1, len(next_st)):
                next_ord = next_st[i]
                index = p[index][next_ord]
                if index == -1:
                    break
            if index != -1:
                s = ''.join([chr(item + ord('a')) for item in now_st])
                if len(s) > self.max_len:
                    self.max_ans = s
                    self.max_len = len(s)
                else:
                    if len(s) == self.max_len:
                        self.max_ans = max(self.max_ans, s)
                return True
            else:
                return False
        
        dfs()
        return self.max_ans








data = Solution()
s = "letsleetcode"
k = 2
print(data.longestSubsequenceRepeatedK(s, k))